A navigation system performs travel guidance for enabling a user to easily reach the selected destination. A typical example is a vehicle navigation system. The present invention is not limited to a vehicle navigation system but is applicable to other types of navigation system such as a PDA (Personal Data Assistant), a cellular phone, and other portable navigation devices. However, for the convenience of explanation, the following description is made mainly for the vehicle navigation system.
Such a navigation system detects the position of the vehicle, reads out map data pertaining to an area at the vehicle current position from a data storage medium, for example, a CD-ROM (compact disk read-only memory) or a DVD (digital versatile disc), and displays a map image on a monitor screen (display) while superposing a mark representing the current location of the vehicle on a predetermined portion of the map image. Alternatively, such map data can be provided to the vehicle from a remote server through a communication network such as Internet.
The vehicle position is determined by a self-contained navigation sensors (e.g. a distance traveled sensor and a bearing sensor) mounted in the vehicle or by a global positioning system (GPS) including an artificial satellite (satellite navigation). The satellite enables absolute position detection and higher position accuracy than the self-contained navigation sensors. However, the satellite navigation involves problem of position detection failure such as in a tunnel or a building where the satellite radio signals are obstructed. Therefore, recent navigation systems utilize both self-contained navigation and satellite navigation to achieve improved performances.
As the present position of the vehicle changes with the travel of the vehicle, the vehicle current position mark in the map image on the screen is changed accordingly. Alternatively, the map is scrolled while the vehicle current position mark is fixed at a predetermined position, for example, at the center of the map image. In either method, the navigation system enables the driver to recognize the map information of the area at the vehicle position at a glance.
When a destination is not set, such a navigation system functions as a locator map which indicates the current location of the vehicle on a map image. When the destination is set, the navigation system starts a route guidance function for setting a guided route from the starting point to the destination. Typically, the route guidance function performs an intersection guidance process in which a monitor screen displays an enlarged intersection diagram and the direction in which the vehicle is to travel while displaying the guide route on a map. When a destination is input, a CPU in the navigation system determines a most suitable guided route from the current vehicle position to the destination and successively stores nodes (expressed in longitude and latitude) constituting the guided route in a memory.
During actual traveling, the node series stored in the memory is searched for a portion of the guided route to be displayed in a map display area of the monitor screen, and the portion of the guided route is highlighted so as to be discriminable from other routes. When the vehicle is within a predetermined distance of an intersection it is approaching, an intersection guidance diagram (an enlarged or highlighted intersection diagram with an arrow indicating the direction in which the vehicle is to turn at the intersection) is displayed to inform a driver of the desired one of roads or directions selectable at the intersection.
FIG. 1A shows an example of a locator map display containing a current vehicle position mark VP on a map image 21. Typically, a navigation system shows the street on which the vehicle is running in the map image 21 and a name of the street such as “W 190TH ST” in an information box 23 on the monitor screen. Other information such as a north pointer NP, a map scale and a current time may also be illustrated on the display screen. In this manner, the locator map display shows the current position of the vehicle on the map image, however, it does not perform the route guidance function because the destination is not set in the navigation system.
FIG. 1B shows an example of route guidance display which performs the route guidance function. The route guidance display is activated after specifying the destination. In this example, the current street “W 190TH ST” and the left side of the next street “PRAIRIE AVE” will be highlighted in the map image 21 to show the direction of turn at the next intersection. In addition, this example further shows an arrow indicating the direction (left) in which the vehicle is to turn at the intersection in a guidance information box 22 at the top of the screen. The guidance information box 22 also shows the name of the street “PRAIRIE AVE” which intersects with the current street “W 190TH ST” and a distance to the intersection. Thus, the navigation system indicates that the vehicle should make a left turn at the intersection with “PRAIRIE AVE”.
Further to the highlighted display, such route guidance is accompanied by voice instructions. If the direction of travel in the next intersection is left, the navigation system gives spoken guidance such as “turn left at the next intersection”. In this example, an information box 24 at the bottom of the display screen includes information regarding the remaining distance to the final destination and an estimated time to reach the final destination.
In order to be guided by the route guidance mode such as shown in FIG. 1B, a destination must be specified in the navigation system so that the system can find one or more routes to get to the destination. FIGS. 2A-2C show examples of display shown on the monitor screen during the operation of inputting the destination.
By operating a menu key, a main menu screen 25 such as shown in FIG. 2A is displayed on the navigation system and a menu item “Destination” is selected from the main menu. This allows the navigation system to display an “Enter Destination by” screen 27 as shown in FIG. 2B for specifying an input method for selecting the destination. The “Enter Destination by” screen 27 lists various methods for selecting the destination including “Address” for specifying the city and address of the destination, “Intersection” for specifying the names of two streets in the city which intersect with one another, and “Point of Interest” (POI) for selecting the programmed destination based on the name, category or telephone number.
Other methods in the “Enter Destination by” screen 27 include “Recent Route” for specifying the destination based on the recent destinations saved in the navigation system, “Address Book” for selecting the address of the destination out of the addresses stored in the system, and “Today's Plan” for specifying two or more destinations in the navigation system. For example, when a user wants to go to several destinations before the final destination, the navigation system calculates an efficient order and routes to such destinations.
When selecting, for example, the “Address” in FIG. 2B, the navigation system displays an “Enter Street Name” screen such as shown in FIG. 2C. The screen of FIG. 2C is basically a key board 38 for inputting the city and address in an address input box 37 on the monitor screen. The user inputs the street name and number in the address input box 37 through the key board 38.
After inputting the destination, the navigation system determines a route to the destination based on, for example, the shortest way to reach the destination, the route using many freeways as possible or the route without using toll road, and the like. Thus, the navigation system moves to the route guidance display such as shown in FIG. lB to guide the user to the destination.
This invention is directed to a method and apparatus for a navigation system using the input method of “Point of Interest” noted above. Typically, a specific category of point of interest (POI) information is searched and displayed based on an order of distance from a current user position. Although the “Point of Interest (POI)” input method is convenient and useful, because the recent storage medium provides a large volume of data showing POI information, it requires a large memory and a relatively long time for extracting and processing the POI information to display the POI information sorted by distance.
An example of process for specifying a destination through the “Point of Interest” is carried out in the following manner with reference to FIGS. 3A-3F. In the example of FIGS. 3A-3F, it is assumed that an intended destination is a Japanese restaurant “Taiko” in Irvine, Calif. FIG. 3A shows an example of screen listing the various input methods noted above for selecting the destination. As shown in this example, typically, the navigation display lists several items, such as up to seven or eight items per page as a maximum number. Therefore, when the number of items exceeds the maximum number, it is usually necessary to scroll the display to see the other items outside of the current screen.
In FIG. 3A, by selecting the “Point of Interest” and hitting an enter key, the navigation system displays a screen shown in FIG. 3B for finding the point of interest by either place names or place types. As shown in this example, this screen typically lists only two items. In FIG. 3B, by selecting the “Place Type” and pressing the enter key, the navigation system displays a screen shown in FIG. 3C for selecting the categories of the point of interest. This screen lists various different categories of point of interest such as “ATM”, “Automotive”, “Bank”, “Restaurant”, “Hotel”, “Shopping” and others. Typically, the number of such categories are as many as forty or more. Therefore, in many cases, such a category list must be scrolled to find a favorite place type on the screen.
By selecting the category type “Restaurant” in FIG. 3C, the navigation system displays another category select screen listing sub-categories of the selected category. In this case, the sub-category screen shows types of food such as “American”, “Californian”, “Chinese”, “French”, “Italian”, “Japanese”, “Korean” and etc. Sometimes, such a sub-category list extends to several pages, requiring page scrolling to find a favorite sub-category.
By selecting the sub-category “Japanese” and pressing the enter key in FIG. 3D, the navigation system displays a screen for selecting a method of finding the places as shown in FIG. 3E. In this example, the methods include “Sort by Distance”, “Name” and “Within a city”. The “Sort by Distance” method is to find the places, Japanese restaurants, in this case, in the order of distance from the vehicle current position. The “Name” method is to find the places by inputting the name of the Japanese restaurant through, for example, a key board. The “Within a City” method is to let users select a city name and then to list the places, i.e., Japanese restaurants within the city.
By selecting the “Sort by Distance” and hitting the enter key in FIG. 3E, the navigation system displays a list of Japanese restaurants in the order of distance from the current vehicle position as shown in FIG. 3F. The screen of FIG. 3F is to select one of the place names in the list. Typically, the list also includes a distance from the current vehicle position and a direction from the current vehicle position for each place name in the list. In the case where two or more restaurants having the same name exist, such restaurants will be listed in the order of the distance from the vehicle position.
The user selects the name “Taiko” in FIG. 3F and presses the enter key. Then, the navigation system displays a confirmation route screen such as shown in FIG. 3G for confirming the destination. The screen of FIG. 3G shows the name, address and phone number of the selected destination. Although not shown in the example of FIG. 3G, such a confirmation screen may also show the distance to the destination, an anticipated time length to reach the destination, and the direction to the destination.
By selecting “OK to Proceed” in FIG. 3G, the navigation system calculates the optimum route to the destination in FIG. 3H. The navigation system determines the route to the destination based on, for example, the shortest way to reach the destination, the route using many freeways as possible or the route without using toll road, and the like. During this process, the navigation system shows a progress of calculation by a bar graph as shown in the lower part of FIG. 3H. Then, the navigation system moves to the route guidance display such as shown in FIG. 1B which performs the route guidance.
In the foregoing example, the process of specifying the destination by the “Point of Interest” (POI) requires a step of searching (extracting) the specified POI information (ex. Japanese restaurant) for an area as large as an entire country. The process further requires a step of sorting the acquired POI information to display in the order of distance from the current vehicle (user) position. In the map data storage medium, such as DVD, an entire area covered by the navigation system is divided into a large number of cells in a manner shown in FIG. 6.
Typically, the navigation system searches the specified POI information for consecutively accessing the cells in a spiral fashion starting from the current vehicle position. The navigation system collects the POI information by spirally and outwardly accessing the cells until either a predetermined number of POIs are collected or all the cells in an entire covering area are searched. For example, the predetermined number of POIs is 1,000. Because the recent storage medium such as DVD provides a large number of cells and a large number of POIs, it requires a relatively long time, such as ten seconds or more to extract the information and to sort the information by distance. Further, because the large volume of information has to be processed, the navigation system has to use a high speed processor and a large memory for temporarily storing the information for the processing.